package kth.csc.inda;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.io.*;

public class Path {
	public static void main(String[] args){
		try{
			new Path(Integer.decode(args[0]),Integer.decode(args[1]));
		}
		catch(NumberFormatException e){
			System.err.println("\nInvalid input "+args[0]+", "+args[1]+" \n"+ e);
		}
	}
	
	private final int from;
	private final int to;
	private ListGraph graph;
	
	public Path(int tempFrom, int tempTo){
		this.from=tempFrom;
		this.to=tempTo;
		LoadGraph();
		if(to>graph.numEdges()||to<0||from>graph.numEdges()||from<0)
			System.err.println("Error, invalid values out of bounds");
		else
			search();
	}
	public void LoadGraph(){
		BufferedReader in = null;
		try {
            in = new BufferedReader(new FileReader("Distances.txt"));
            String line;
            while ((line = in.readLine()) != null) {
            	String[] lineStrings = line.split(" ");
            	boolean edge=false;
            	int edgeStart=-1, edgeEnd=-1, edgeCost=-1;
            	for(String s : lineStrings){
            		try{
	            		if(s.equals("//")){
	            			break;
	            		}
	            		else if(s.equals("")){
	            			break;
	            		}
	            		else if(graph==null){
	            			graph = new ListGraph(Integer.decode(s));
	            			break;
	            		}
	            		if(edgeStart==-1){
	            			edgeStart=Integer.decode(s);
	            		}
	            		else if(edgeEnd==-1){
	            			edgeEnd=Integer.decode(s);
	            		}
	            		else if(edgeCost==-1){
	            			edge=true;
	            			edgeCost=Integer.decode(s);
	            		}	
            		}
            		catch(Exception e){
            			System.err.println("Distances.txt invalid data "+e);
            		}
            	}
            	if(edge&&(edgeStart==-1|edgeEnd==-1|edgeCost==-1)){
            		System.err.println("Distances.txt invalid data");// {["+edgeStart+"],["+edgeEnd+"],["+edgeCost+"],");
            	}
            	else if(edge){
            		graph.addEdge(edgeStart, edgeEnd, edgeCost);
            	}
            }
        } catch (FileNotFoundException e) {
            System.err.println("File not found! "+e);
        } catch (IOException e) {
            System.err.println("IOException "+e);
		} finally {
	        try {
	            if (in != null) 
	                in.close();
	        } catch (IOException e) {
	            System.err.println("IOException "+e);
	        }
	        System.out.println(graph.toString());
	    }



	}
	private class PathWay{
		String s="";
		public void add(String r){
			s=s+""+r;
		}
		public String get(){
			return s;
		}
	}
	public void search(){
		PathWay[] way = new PathWay[graph.numVertices()];
		for(int i =0;i<graph.numVertices();i++){
			way[i] = new PathWay();
		}
		HashSet<Integer> set = new HashSet<Integer>();
	    Queue<Integer> Q = new LinkedList<Integer>();
	    Q.add(from); // Add v to end of queue
	    set.add(from);
	    way[from].add(""+from);
	    while(!Q.isEmpty()){
	        int a = Q.remove(); // Remove v from top of queue.
	        if(a==to){
	        	System.out.println("The path from "+from+" to "+to+" could be:");
	        	System.out.println(way[a].get());
	        	return;
	        }
	        set.add(a);
	        // Here you may perform some operation on a.
	        VertexIterator vrt = graph.adjacentVertices(a);
	        while(vrt.hasNext()){
	        	int next=vrt.next();
	        	if(!set.contains(next)){
	        		way[next].add(""+way[a].get()+" "+next);
	        		Q.add(next);
	        		set.add(next);
	        		//System.out.println(""+next);
	        	}
	        }
	            
	    }
	    System.err.println("no way found from "+from+" to "+to);
	}
}
